#define _CRT_SECURE_NO_WARNINGS 1
/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */
typedef struct Node Node;
Node* BuyNode(int x) {
    Node* newnode = (Node*)malloc(sizeof(Node));
    newnode->val = x;
    newnode->next = newnode->random = NULL;
    return newnode;
}
void AddNode(Node* head) {
    Node* pcur = head;
    while (pcur) {
        Node* newnode = BuyNode(pcur->val);
        newnode->next = pcur->next;
        pcur->next = newnode;
        pcur = pcur->next->next;
    }
}
void Frandom(Node* head) {
    Node* pcur = head;
    Node* cur, * copy;
    cur = head;
    copy = cur->next;
    while (cur) {
        if (cur->random)
            copy->random = cur->random->next;


        cur = copy->next;
        if (copy->next) {
            copy->next = copy->next->next;
            copy = copy->next;
        }
    }
}
struct Node* copyRandomList(struct Node* head) {
    Node* pcur = head;
    if (head == NULL) {
        return pcur;
    }
    AddNode(head);
    Frandom(head);
    return head->next;
}